interface TreeNode {
	val: number;
	left: TreeNode | null;
	right: TreeNode | null;
}

const treeHeightMap = new Map<TreeNode, number>();

function getTreeHeight(root: TreeNode | null): number {
	if (root === null) return 0;

	const cachedHeight = treeHeightMap.get(root);
	if (cachedHeight !== undefined) return cachedHeight;

	const leftTreeHeight = getTreeHeight(root.left);
	const rightTreeHeight = getTreeHeight(root.right);

	const height = Math.max(leftTreeHeight, rightTreeHeight) + 1;
	treeHeightMap.set(root, height);
	return height;
}

/**
 * **[110. 平衡二叉树](https://leetcode.cn/problems/balanced-binary-tree/)**
 *
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 *
 * @param root
 * @returns
 */
export default function isBalanced(root: TreeNode | null): boolean {
	if (root === null) return true;

	if (Math.abs(getTreeHeight(root.left) - getTreeHeight(root.right)) > 1) return false;

	return isBalanced(root.left) && isBalanced(root.right);
}
